|
In graph theory, series-parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits. ==Definition and terminology== In this context, the term graph means multigraph. There are several ways to define series-parallel graphs. The following definition basically follows the one used by David Eppstein. A two-terminal graph (TTG) is a graph with two distinguished vertices, ''s'' and ''t'' called ''source'' and ''sink'', respectively. The parallel composition ''Pc = Pc(X,Y)'' of two TTGs ''X'' and ''Y'' is a TTG created from the disjoint union of graphs ''X'' and ''Y'' by merging the sources of ''X'' and ''Y'' to create the source of ''Pc'' and merging the sinks of ''X'' and ''Y'' to create the sink of ''Pc''. The series composition ''Sc = Sc(X,Y)'' of two TTGs ''X'' and ''Y'' is a TTG created from the disjoint union of graphs ''X'' and ''Y'' by merging the sink of ''X'' with the source of ''Y''. The source of ''X'' becomes the source of ''Sc'' and the sink of ''Y'' becomes the sink of ''Sc''. A two-terminal series-parallel graph (TTSPG) is a graph that may be constructed by a sequence of series and parallel compositions starting from a set of copies of a single-edge graph ''K2'' with assigned terminals. ''Definition 1''. Finally, a graph is called series-parallel (sp-graph), if it is a TTSPG when some two of its vertices are regarded as source and sink. In a similar way one may define series-parallel digraphs, constructed from copies of single-arc graphs, with arcs directed from the source to the sink. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Series-parallel graph」の詳細全文を読む スポンサード リンク
|